﻿#include <iostream>
#include "BinaryTree.h"

static int posible(int remainCount)
{
    if (remainCount == 0 || remainCount == 1) return 1;

    int total = 0;
    for (int leftNodeCount = 0; leftNodeCount <= remainCount - 1; leftNodeCount++)
    {
        total += posible(leftNodeCount) * posible(remainCount - 1 - leftNodeCount);
    }

    return total;
}

static int byStrictTable(int remainCount)
{
    if (remainCount == 0 || remainCount == 1) return 1;

    int* dp = (int*)malloc(sizeof(int) * (remainCount + 1));
    memset(dp, 0, sizeof(int) * (remainCount + 1));
    dp[0] = 1;
    dp[1] = 1;
    for (int n = 2; n <= remainCount; n++)
    {
        int total = 0;
        for (int leftNodeCount = 0; leftNodeCount <= n - 1; leftNodeCount++)
        {
            total += dp[leftNodeCount] * dp[n - 1 - leftNodeCount];
        }

        dp[n] = total;
    }

    return dp[remainCount];
}

// 给定一个非负整数n，代表二叉树的节点个数。返回能形成多少种不同的二叉树结构。
//
// 假设有1个，则只有一种结构，就是单个根节点；有2个，则可能有2种结构:
//
//   root    root
//    /        \
// left        right
//
//假设有N个，则可能的情况是：
//   root          root           root         root
//   /    \        /    \         /    \        /   \
//  0   N - 1     1    N - 2     2    N - 3    3   N - 4  ...
int main_HowManyTreesByN()
{
    for (int n = 0; n < 20; n++)
    {
        printf("n=%d, %d, %d\n", n, posible(n), byStrictTable(n));
    }

    return 0;
}